/**************************************************************
*   This software is confidential and contains code, algorithms 
* and know-how proprietary to Saber Interactive.
*
* Copyright (c), Saber Interactive, Inc. 2001-2011
***************************************************************
*
* DS_VECTOR.h
*
* DS implementation of STL's vector
***************************************************************/
#ifndef _DS_VECTOR_H_
#define _DS_VECTOR_H_

#pragma once

//#include "ap/ap_dlstat.h"
#include "ds\ds_comm.h"

// variable size array of elements of type T. T MUST BE MOVABLE by memcpy !!!
template <class T, UINT ALIGNMENT=8> 
class dsVECTOR {
public:
                     dsVECTOR            (/*AP_CL_DECL*/);
   explicit          dsVECTOR            (int size/*, AP_CL_DECL*/);
                     dsVECTOR            (int size, const T &value/*, AP_CL_DECL*/);
                     dsVECTOR            (const dsVECTOR &src/*, AP_CL_DECL*/); // no ap_cl, otherwise CRASH! (:
                     dsVECTOR            (const T *begin, int num/*, AP_CL_DECL*/);
                    ~dsVECTOR            (void);

   const dsVECTOR&  operator =           (const dsVECTOR &src);

   void              Swap                 (dsVECTOR &arr);

   BOOL              IsEmpty              (void) const { return nElem == 0; }
   int               Length               (void) const { return nElem; }
   int               Capacity             (void) const { return allocated; }
   void              Resize               (int newSize);
   void              Resize               (int newSize, const T &fillValue);
   void              ShrinkResize         (int newSize);
   void              GrowResize           (int newSize);
   void              GrowResize           (int newSize, const T &fillValue);
   void              GrowResize_NoNew     (int newSize);
   void              Reserve              (int newCapacity);
   void              Compact              (void);
   void              Free                 (void) { Realloc(0); }
   BOOL              IsValidIdx           (int idx) const { return (idx >= 0 && idx < nElem); }
   
   void              Clear                (void);

   const T&          Front                (void) const;
   T&                Front                (void);
   const T&          Back                 (void) const;
   T&                Back                 (void);

   const T&          Back                 (int index) const;
   T&                Back                 (int index);

   const T*          Begin                (void) const { return pData; }
   T*                Begin                (void) { return pData; }

   const T*          End                  (void) const { return pData + nElem; }
   T*                End                  (void) { return pData + nElem; }

   void              Append               (const dsVECTOR<T,ALIGNMENT>& vec) { Insert(Length(),vec.Begin(),vec.Length()); }
   void              Insert               (int pos, const T &val, int num = 1);
   void              Insert               (int pos, const T *begin, int num);
   void              Erase                (int pos, int num = 1);
   void              EraseNonSorted       (int pos);

   T&                PushBack             (const T &val = T());
   void              PopBack              (void);

   const T&          operator []          (int idx) const;
   T&                operator []          (int idx);

   void              Sort                 (void)                  { Sort(dsCMP(), dsSWAP<T>()); }
   void              InvSort              (void)                  { InvSort(dsCMP(), dsSWAP<T>()); }

   template <class KEY>
   int               Find                 (const KEY &key) const  { return Find(key, dsCMP()); }

   template <class CMP> 
   void              Sort                 (const CMP & cmp)       { Sort(cmp, dsSWAP<T>()); }

   template <class CMP, class SWAP> 
   void              Sort                 (const CMP &cmp, const SWAP &swap);

   template <class CMP> 
   void              InvSort              (const CMP & cmp)       { InvSort(cmp, dsSWAP<T>()); }

   template <class CMP, class SWAP> 
   void              InvSort              (const CMP &cmp, const SWAP &swap);

   enum INS_SORT{INS_DUP_REPLACE, INS_DUP_IGNORE, INS_DUP_ERROR, INS_DUP_RIGHT};

   int               InsertSorted         (const T & val, INS_SORT dup = INS_DUP_IGNORE) { return InsertSorted(val, dsCMP(), dup); }
   template <class CMP>
   int               InsertSorted         (const T &val, const CMP &cmp, INS_SORT dup = INS_DUP_IGNORE);

   template <class KEY>
   int               FindSorted           (const KEY & key) const { return FindSorted(key, dsCMP()); }
   template <class CMP, class KEY>
   int               FindSorted           (const KEY &key, const CMP &cmp) const;
   template <class CMP, class KEY>
   int               FindSortedFirst      (const KEY &key, const CMP &cmp) const;
   template <class CMP, class KEY>
   int               FindSortedLastLess   (const KEY &key, const CMP &cmp) const;
   template <class CMP, class KEY>
   int               FindSortedFirstGE    (const KEY &key, const CMP &cmp) const;
   template <class CMP, class KEY>
   int               FindSortedFirstGreater(const KEY &key, const CMP &cmp) const { return FindSortedFirstGreater(key, cmp, 0, nElem - 1); }
   template <class CMP, class KEY>
   int               FindSortedFirstGreater(const KEY &key, const CMP &cmp, int begin, int end) const;
   template <class CMP, class KEY>
   int               FindLowerBound       (const KEY &key, const CMP &cmp) const;
   template <class CMP, class KEY>
   int               Find                 (const KEY &key, const CMP &cmp, int startPos = 0) const;

   template <class CMP>
   void              Difference          (const dsVECTOR &arr1,const  dsVECTOR &arr2, const CMP &cmp);

   template <class CMP>
   void              Common              (const dsVECTOR &arr1,const  dsVECTOR &arr2, const CMP &cmp);

   template <class CMP>
   void              MergeSorted          (const dsVECTOR &arr1, const dsVECTOR &arr2, const CMP &cmp);

   template <class CMP>
   void              MergeSortedUnique    (const dsVECTOR &arr1, const dsVECTOR &arr2, const CMP &cmp);

   T &               operator +=          (const T & key);

   // memory statistics block (for correct taking into acount arrays and vectors of vectors
#ifdef AP_USE_MEM_STAT
   template <typename T1> 
   T1*                CallNew (T1 *t) { return New(t); }

   template <typename T1>
   dsVECTOR<T1>*      CallNew (dsVECTOR<T1> *t) { return new(t) dsVECTOR<T1>(__cl); }

   void              UpdateCL             (apCL cl) { __cl = cl; }
#endif

   // Construct dsVECTOR from provided data
   void              Construct(T *dataPtr, int numElem, int allocatedNum) { pData = dataPtr; nElem = numElem; allocated = allocatedNum; }

protected:
   void              Realloc              (int size);
   void             _internalRealloc      (int size);
   void             _internalFree         (void *p);

   template <class CMP, class SWAP> 
   void              HeapSort             (const CMP &cmp, const SWAP &swap);

   template <class CMP, class SWAP> 
   void              Sisp                 (int p, int q, T * array, const CMP & cmp, const SWAP & swap);

   T        *pData;
   int       nElem, allocated;
#ifdef AP_USE_MEM_STAT
   apCL    __cl;
#endif
};

#ifdef AP_USE_MEM_STAT
   template <typename T, UINT ALIGNMENT>
   void apMemoryUpdateCL (dsVECTOR<T, ALIGNMENT> *vect, int size, apCL cl) 
   {
      for (int i = 0; i < size; i++) {
         vect[i].UpdateCL(cl);
      }

      return ;
   }
#else
   #define  apMemoryUpdateCL(vect, size, cl)  ((void)0)
#endif

template <class KEY, class VAL> 
class dsPAIR<KEY, dsVECTOR<VAL> > {
public:
   KEY           key;
   dsVECTOR<VAL> val;

   dsPAIR (void) : val {}
   dsPAIR (const KEY &k, const dsVECTOR<VAL> &v) : key(k), val(v)   {}
};

template <class T> 
class dsARRAY {
public:
   dsARRAY              (/*AP_CL_DECL*/);
   explicit dsARRAY     (int size/*, AP_CL_DECL*/);
   dsARRAY              (int size, const T &value/*, AP_CL_DECL*/);
   dsARRAY              (const dsARRAY &src); // no ap_cl, otherwise CRASH! (:
   ~dsARRAY             (void);

   const dsARRAY&  operator =             (const dsARRAY &src);

   void              Swap                 (dsARRAY &arr);

   BOOL              IsEmpty              (void) const { return nElem == 0; }
   int               Length               (void) const { return nElem; }
   void              Resize               (int newSize);
   void              Resize               (int newSize, const T &fillValue);
   BOOL              IsValidIdx           (int idx) const { return (idx >= 0 && idx < nElem); }

   const T*          Begin                (void) const { return pData; }
   T*                Begin                (void) { return pData; }
   const T*          End                  (void) const { return pData + nElem; }
   T*                End                  (void) { return pData + nElem; }

   const T&          operator []          (int idx) const;
   T&                operator []          (int idx);

   // memory statistics block (for correct taking into acount arrays and vectors of vectors
#ifdef AP_USE_MEM_STAT
   template <typename T1> 
   T1*                CallNew (T1 *t) { return New(t); }

   template <typename T1>
   dsARRAY<T1>*       CallNew (dsARRAY<T1> *t) { return new(t) dsARRAY<T1>(__cl); }

   void               UpdateCL             (apCL cl) { __cl = cl; }
#endif

protected:
   void              Realloc              (int size);
   void             _internalFree         (void *p);

   T        *pData;
   int       nElem;
#ifdef AP_USE_MEM_STAT
   apCL    __cl;
#endif
};

#include "ds_algorithm.h"
#include "ds_vector.hpp"

#endif
